/* 费用流 算法应用
* 1.基础概念
    费用流即最小/大费用最大流（即最大可行流中的最小/大费用）
    费用流：最大流时每条边上的可行流×该边上的费用

* 2.求解算法
    将 EK 算法中的 bfs 改为 spfa，spfa 用来求解源点 S 到 T 的最短/长路（即 S 到 T 上的最小路径费用和）
    在求最短/长路的同时找到一条增广路径，然后增加这部分的费用，直到找不到增广路径为止

    spfa不可处理负权回路，如果图中有负权回路，需要消圈

    只要当前沿着最短路径增广，则一定能求得最小费用流

* 本题:
    货物->流
    仓库容量>平均值 左侧 向仓库连容量为 ai-平均值 的边，费用为0

    仓库容量<平均值 右侧 向仓库连容量为 平均值-ai 的边，费用为0

    每个点向相邻的点连边，容量为正无穷，费用为1，表示1次搬运量

*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110, M = 30010, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], c[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int capa[N]; //仓库容量

void AddEdge(int a, int b, int cc, int ww)
{
    e[idx] = b, c[idx]=cc, w[idx]=ww, ne[idx]=h[a], h[a]=idx++;
    e[idx] = a, c[idx]=0, w[idx]=-ww, ne[idx]=h[b], h[b]=idx++;
}

bool spfa() 
{
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);

    int hh=0, tt=0;
    q[tt++]=S, d[S]=0, incf[S]=INF;

    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N) hh=0;
        st[u]=false;

        for(int i=h[u]; ~i; i=ne[i])
        {
            int v=e[i];
            if(c[i] && d[v] > d[u]+w[i])
            {
                d[v] = d[u]+w[i];
                incf[v] = min(incf[u], c[i]);
                pre[v] = i;
                if(!st[v])
                {
                    st[v] = true; //如果之前没有访问过，则置已访问，除非有多条边可指向v，即在队列中有多次入队
                    q[tt++] = v;
                    if(tt==N) tt=0;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK() 
{
    int cost=0;
    while(spfa())
    {
        cost+=incf[T]*d[T]; //当前流的最值流
        for(int i=T; i!=S; i=e[pre[i]^1])
        {
            c[pre[i]] -= incf[T]; c[pre[i]^1] += incf[T]; 
        }

    }
    return cost;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
    #else
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif
    memset(h, -1, sizeof h);

    cin >> n;
    S=0, T=n+1;
    int sum = 0;
    for(int i=1; i<=n; i++)
    {
        cin >> capa[i];
        sum += capa[i];

        //从每个仓库向相邻两个仓库连边，容量为INF，费用为1
        AddEdge(i, i<n?i+1:1, INF, 1); //环形图
        AddEdge(i, i>1?i-1:n, INF, 1);

    }

    int avg = sum/n;
    for(int i=1; i<=n; i++)
    {
        if(capa[i] >= avg) AddEdge(S, i, capa[i]-avg, 0);
        else AddEdge(i, T, avg-capa[i], 0);
    }

    printf("%d\n", EK());
    return 0;
}